//
// Created by hitfyd on 18-4-26.
//
#include <bits/stdc++.h>

using namespace std;

const int XNum = 1000, FNum = XNum;
vector<pair<int, int>> X;//有限集X，每个元素代表一个点并按照在向量中的顺序编号代表
vector<set<int>> F, C;//子集合集F，每个子集中存储点的编号;子集合集C，即为最后的输出
set<int> selectset, unselectset;//已选择点的集合和尚未被选择点的集合
const int subsetsize = 20;//子集合包含点的最大个数

//初始化已选择点的集合（清空）和尚未被选择点的集合（全集，等于X）
void initSelected(){
    selectset.clear();
    unselectset.clear();
    for (int i = 0; i < XNum; i++)
        unselectset.insert(i);
}

void createRandomNodes() {
    set<pair<int, int>> nodeset;
    int times = 0;
    while (nodeset.size() < XNum) {
        nodeset.insert(pair<int, int>(rand() % 100, rand() % 100));
        times++;
    }
    X.clear();
    copy(nodeset.begin(), nodeset.end(), back_inserter(X));
    printf("The times of generating random points:%d\n", times);

    F.clear();
    set<int> subset;
    initSelected();
    int n, x;
    //选出S0中的20个元素
    while (subset.size() < subsetsize) {
        int i = rand() % XNum;
        subset.insert(i);
        selectset.insert(i);
        unselectset.erase(i);
    }
    F.push_back(subset);
    //找到集合
    while (unselectset.size() >= subsetsize) {
        n = rand() % subsetsize;
        if(n == 0)
            x = 0;
        else
            x = rand() % n;
        subset.clear();
        while (subset.size() < x) {
            int i = rand() % XNum;
            if (unselectset.find(i) != unselectset.end()) {
                subset.insert(i);
                selectset.insert(i);
                unselectset.erase(i);
            }
        }
        while (subset.size() < n) {
            int i = rand() % XNum;
            if (selectset.find(i) != selectset.end())
                subset.insert(i);
        }
        F.push_back(subset);
    }
    F.push_back(unselectset);
    while (F.size() < FNum) {
        subset.clear();
        n = rand() % subsetsize;
        while (subset.size() < n) {
            subset.insert(rand() % XNum);
        }
        F.push_back(subset);
    }
}

void printSet(set<int> &s) {
    printf("set size:\t%ld\t", s.size());
    set<int>::iterator it = s.begin();
    while (it != s.end()) {
        printf("%d, ", *it);
        it++;
    }
    printf("\n");
}

void printVectorSet(vector<set<int>> &F) {
    printf("vector size:\t%ld\n", F.size());
    vector<set<int>>::iterator it = F.begin();
    while (it != F.end()) {
        printSet(*it);
        it++;
    }
}

bool verify(){
    set<int> allset;
    for(int i = 0; i < C.size(); i++){
        set<int>::iterator it = C[i].begin();
        while (it != C[i].end()) {
            allset.insert(*it);
            it++;
        }
    }
    if(allset.size() == XNum)
        return true;
    return false;
}

void Set_Cover_Approx(){
    initSelected();
    C.clear();
    while(!unselectset.empty()){
        int maxindex = 0, maxweight = INT_MIN;
        for(int i = 0; i < F.size(); i++){
            int unselectweight = 0;
            set<int>::iterator it = F[i].begin();
            while(it != F[i].end()){
                if(unselectset.find(*it) != unselectset.end())
                    unselectweight++;
                it++;
            }
            if(unselectweight > maxweight){
                maxindex = i;
                maxweight = unselectweight;
            }
        }
//        printSet(F[maxindex]);
        set<int>::iterator it = F[maxindex].begin();
        while(it != F[maxindex].end()){
            unselectset.erase(*it);
            it++;
        }
        C.push_back(F[maxindex]);
    }
}

int main() {
    clock_t startTime, endTime;
    createRandomNodes();
    startTime = clock();
    Set_Cover_Approx();
    endTime = clock();
    printVectorSet(F);
    printf("\n\n\n\n\n");
    printVectorSet(C);
    printf("%ld\t%ld\t%ld\n", startTime, endTime, CLOCKS_PER_SEC);
    printf("Algorithm run time:\t%lfms\n", (double)(endTime - startTime) / CLOCKS_PER_SEC * 1000);
    printf("C集合大小： %ld,\tVerify Result: %s\n", C.size(), verify() == true ? "True" : "False");
    return 0;
}